package solution;

import java.util.Vector;

import jigsaw.Jigsaw;
import jigsaw.JigsawNode;


/**
 * 在此类中填充算法，完成重拼图游戏（N-数码问题）
 */
public class Solution extends Jigsaw {
	private Vector<JigsawNode> openList;  // open表 ：用以保存已发现但未访问的节点
    private Vector<JigsawNode> closeList; // close表：用以保存已访问的节点
    /**
     * 拼图构造函数
     */
    public Solution() {
    }

    /**
     * 拼图构造函数
     * @param bNode - 初始状态节点
     * @param eNode - 目标状态节点
     */
    public Solution(JigsawNode bNode, JigsawNode eNode) {
        super(bNode, eNode);
    }

    /**
     *（实验一）广度优先搜索算法，求指定5*5拼图（24-数码问题）的最优解
     * 填充此函数，可在Solution类中添加其他函数，属性
     * @param bNode - 初始状态节点
     * @param eNode - 目标状态节点
     * @return 搜索成功时为true,失败为false
     */
    public boolean BFSearch(JigsawNode bNode, JigsawNode eNode) {
        beginJNode = bNode;
        endJNode = eNode;
        openList = new Vector<JigsawNode>();
        closeList = new Vector<JigsawNode>();
        openList.addElement(beginJNode);
        currentJNode = beginJNode;
        int sNum = 0;
        
        while (!openList.isEmpty()) {
        	if (openList.firstElement().equals(endJNode)) {
        		getPath();
        		break;
        	}
        	else {
        		closeList.addElement(openList.firstElement());
        		Vector<JigsawNode> findAdjacent = new Vector<JigsawNode>();
        		JigsawNode tJNode;
        		for (int i = 0; i < 4; i++) {
        			tJNode = new JigsawNode(openList.firstElement());
        			if (tJNode.move(i) && !closeList.contains(tJNode) && !openList.contains(tJNode)) {
        				findAdjacent.addElement(tJNode);
        			}
        		}
                for (JigsawNode node : findAdjacent) {  
                    openList.addElement(node);  
                }
                openList.remove(0);
                currentJNode = openList.firstElement();
                closeList.addElement(currentJNode);
                sNum++;
        	}
        }
        System.out.println("Jigsaw AStar Search Result:");
        System.out.println("Begin state:" + this.getBeginJNode().toString());
        System.out.println("End state:" + this.getEndJNode().toString());
        // System.out.println("Solution Path: ");
        // System.out.println(this.getSolutionPath());
        System.out.println("Total number of searched nodes:" + sNum);
        System.out.println("Depth of the current node is:" + this.getCurrentJNode().getNodeDepth());
        return this.isCompleted();
    }


    /**
     *（Demo+实验二）计算并修改状态节点jNode的代价估计值:f(n)
     * 如 f(n) = s(n). s(n)代表后续节点不正确的数码个数
     * 此函数会改变该节点的estimatedValue属性值
     * 修改此函数，可在Solution类中添加其他函数，属性
     * @param jNode - 要计算代价估计值的节点
     */
    public void estimateValue(JigsawNode jNode) {
    	// 后续节点不正确的数码个数
    	int s = 0;
        int dimension = JigsawNode.getDimension();
        for (int index = 1; index < dimension * dimension; index++) {
            if (jNode.getNodesState()[index] + 1 != jNode.getNodesState()[index + 1]) {
                s++; 
            }
        }
        int distance = 0;
        int geometry = 0;
        for (int i = 1; i <= dimension * dimension; i++) {
        	for (int j = 1; j <= dimension * dimension; j++) {
        		if (jNode.getNodesState()[i] != 0 && jNode.getNodesState()[i] == endJNode.getNodesState()[j]) {
        			int x1 = (i - 1) / 5;  
                    int y1 = (i + 4) % 5;  
                    int x2 = (j - 1) / 5;  
                    int y2 = (j + 4) % 5;  
                    int xManhaton = ( x1 >= x2 ? x1 - x2 : x2 - x1 );  
                    int yManhaton = ( y1 >= y2 ? y1 - y2 : y2 - y1 );
                    distance += xManhaton;
                    distance += yManhaton;
                    geometry += Math.sqrt(xManhaton * xManhaton + yManhaton * yManhaton);
                    break;
        		}
        	}
        }
        int av = (int)(s * 1 + distance * 2 + geometry * 3);  
        jNode.setEstimatedValue(av);
    }
}
